package com.kevin.Code.SlidingWindow;

import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * @author Vinlee Xiao
 * @Classname SlidingWindowMaximum
 * @Description Leetcode 239. 滑动窗口最大值 难度 困难 也没啥思路
 * @Date 2021/10/22 19:44
 * @Version 1.0
 */
public class SlidingWindowMaximum {

    /**
     * 先用暴力法 再去优化 超过时间限制
     * 自己思路
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {

        int len = nums.length;

        if (k == 1) {
            return nums;
        }

        //返回数组的大小
        int[] result = new int[len - k + 1];
        int index = 0;
        for (int i = 0; i <= len - k; i++) {
            //本次中结束的标记
            int endIndex = i + k - 1;
            int maxValue = nums[i];
            for (int j = i + 1; j <= endIndex; j++) {
                if (nums[j] > maxValue) {
                    maxValue = nums[j];
                }
            }
            result[index] = maxValue;
            index++;
        }

        return result;
    }

    /**
     * 优化暴力方法 依然是暴力法
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
        int len = nums.length;
        if (k == 1) {
            return nums;
        }
        int maxValue = nums[0];
        for (int i = 0; i < k; i++) {
            if (maxValue < nums[i]) {
                maxValue = nums[i];
            }
        }
        //返回数组的大小
        int[] result = new int[len - k + 1];
        int index = 0;
        for (int i = 0; i <= len - k; i++) {
            //本次中结束的标记
            int endIndex = i + k - 1;

            if (nums[endIndex] > maxValue) {
                maxValue = nums[endIndex];
                result[index] = maxValue;
                index++;
                continue;
            }
            //重新对最大k数组中的最
            maxValue = nums[i];
            for (int j = i + 1; j <= endIndex; j++) {
                if (nums[j] > maxValue) {
                    maxValue = nums[j];
                }
            }
            result[index] = maxValue;
            index++;
        }

        return result;
    }

    /**
     * 官方题解：优先队列
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow2(int[] nums, int k) {

        if (k == 1) {
            return nums;
        }
        int len = nums.length;
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o1[1];
            }

        });

        int[] result = new int[len - k + 1];
        for (int i = 0; i < k; i++) {
            //向队列输入每一对数组 值：索引
            priorityQueue.offer(new int[]{nums[i], i});
        }

        int index = 0;
        result[index++] = priorityQueue.peek()[0];
        for (int i = k; i < len; i++) {
            //继续向队列中输出
            priorityQueue.offer(new int[]{nums[i], i});
            //如果当前队列的堆顶元素对应的下标 小于当前滑动窗口边界的左边边界 则出堆
            while (priorityQueue.peek()[1] <= i - k) {
                //出堆
                priorityQueue.poll();
            }
            result[index++] = priorityQueue.peek()[0];
        }

        return result;
    }

    /**
     * 双端队列 官方题解
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow3(int[] nums, int k) {
        if (k == 1) {
            return nums;
        }

        int len = nums.length;
        Deque<Integer> deque = new LinkedList<>();

        int[] result = new int[len - k + 1];
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {

                deque.pollLast();
            }
            //向队列队尾插入坐标
            deque.addLast(i);
        }
        int index = 0;
        result[index++] = deque.peekFirst();

        for (int i = k; i < len; i++) {
            //使队列中的数据服从对头到队尾 从大从小
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            //将当前元素加入队尾
            deque.addLast(i);
            //对队头的下标进行检查 看其是否在当前滑动窗口边界的左边
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            //将对头的元素加入到结果数组中
            result[index++] = nums[deque.peekFirst()];

        }
        return result;
    }

    public static void main(String[] args) {
        SlidingWindowMaximum slidingWindowMaximum = new SlidingWindowMaximum();
        int[] nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7, 3};

        int[] res = slidingWindowMaximum.maxSlidingWindow1(nums, 3);
        for (int i : res) {
            System.out.print(i + " ");
        }
    }
}
